
SubstractNetwork::SubstractNetwork( const char* in_file, const char* mode = "\0" ) : Network( in_file ){
	srand(time(NULL));
	
	verbose = (!strcmp( mode, "v" ) ) ? true : false;
	
	sum_prizes_attended_requests = 0;
	total_attended_requests = 0;
}

SubstractNetwork::~SubstractNetwork(){
	while( schedule_queue.size() ){
		delete schedule_queue.front().vn;
		schedule_queue.pop_front();
	}
	
	while( active_vns.size() ){
		delete active_vns.front().vn;
		active_vns.pop_front();
	}
}

void SubstractNetwork::setPrioritySystem( PrioritySystem ps ){
	priority_system = ps;
}

void SubstractNetwork::setAllocationSystem( AllocationSystem as ){
	allocation_system = as;
}

int SubstractNetwork::getSumPrizesAttendedRequests(){
	return sum_prizes_attended_requests;
}
	
int SubstractNetwork::getTotalAttendedRequests(){
	return total_attended_requests;
}

void SubstractNetwork::pushInScheduleQueue( VirtualNetwork* vn, int vn_id ){
	struct ScheduleElement se;
	se.vn_id = vn_id;
	se.real_prize = vn->getPrize();
	se.vn = vn;
	schedule_queue.push_back( se );
}

void SubstractNetwork::popFromScheduleQueue( int vn_id ){
	list<struct ScheduleElement>::iterator it = schedule_queue.begin();
	while( it != schedule_queue.end() ) {
		if( it->vn_id == vn_id  ){
			delete it->vn;
			schedule_queue.erase( it );
			if( verbose )
				cout << "Time expired: VN " << vn_id << " could not be allocated" << endl;
			return;
		}
		++it;
	}
}

void SubstractNetwork::deallocateVirtualNetwork( int vn_id ){
	
	list<struct ScheduleElement>::iterator it1 = active_vns.begin();
	while( it1 != active_vns.end() ) {
		if( it1->vn_id == vn_id  ){

			qsort( nodes, m, sizeof( struct Node ), compareIds );
			
			struct Node* vn_nodes = it1->vn->getNodeList();
			int vn_m = it1->vn->getNumberOfNodes();
			
			for( int i = 0; i < vn_m; ++i ){
				if( vn_nodes[i].target_node != -1 ){
					nodes[vn_nodes[i].target_node].processing += vn_nodes[i].processing;
					vn_nodes[i].target_node = -1;
				}
			}
			
			Edge*** vn_graph = it1->vn->getGraph();
			for( int i = 0; i < vn_m; ++i ){
				for( int j = i; j < vn_m; ++j ){
					if( vn_graph[i][j] != NULL ){
						if( vn_graph[i][j]->sn_path != NULL ){
							list<int>::iterator v1, v2;
							v1 = v2 = vn_graph[i][j]->sn_path->begin();
							++v2;
							while( v2 != vn_graph[i][j]->sn_path->end() ){
								graph[*v1][*v2]->bandwidth += vn_graph[i][j]->bandwidth;
								graph[*v2][*v1]->bandwidth += vn_graph[i][j]->bandwidth;
								++v2; ++v1;
							}
						}
					}
				}
			}
			
			delete it1->vn;
			active_vns.erase( it1 );
			return;
		}
		++it1;
	}
}

void SubstractNetwork::scheduler(){
	updateRealPrizes();
	sortVirtualNetworks();
	
	/*PRINT SCHEDULE QUEUE
	list<struct ScheduleElement>::iterator it2 = schedule_queue.begin();
	while( it2 != schedule_queue.end() ) {
		cout << it2->real_prize << " ";
		++it2;
	}
	cout << endl;
	//*/
	
	list<struct ScheduleElement>::iterator it = schedule_queue.begin();
	while( it != schedule_queue.end() ){
		
		//*with expiration time
		if( allocateVirtualNetwork( *it ) )
			it = schedule_queue.erase( it );
		else
			++it;
		//*/
		
		/*without expiration
		if( !allocateVirtualNetwork( *it ) )
			delete it->vn;
		it = schedule_queue.erase( it );
		//*/
		
		
		
	}
}

void SubstractNetwork::updateRealPrizes(){
	switch( priority_system ){
		case ArrivalOrder:{
			//do nothing
			break;
		}
		case MostPrizeFirst:{
			list<struct ScheduleElement>::iterator it = schedule_queue.begin();
			while( it != schedule_queue.end() ) {
				it->real_prize = it->vn->getPrize();
				++it;
			}
			break;
		}
		default:{
			cerr << "Error in updateRealPrizes function: Undefine priority system" << endl;
			exit(-1);
		}
	}
}

void SubstractNetwork::sortVirtualNetworks(){
	switch( priority_system ){
		case ArrivalOrder:{
			//do nothing
			break;
		}
		case MostPrizeFirst:{
			schedule_queue.sort( mostPrizeFirst );
			break;
		}
		default:{
			cerr << "Error in sortVirtualNetworks function: Undefine priority system" << endl;
			exit(-1);
		}
	}
}

bool SubstractNetwork::allocateVirtualNetwork( struct ScheduleElement se ){
	switch( allocation_system ){
		case Greedy:{
			return greedyMethod( se );
			break;
		}
		case TabuSearch:{
			return tabuSearch( se );
			break;
		}
		default:{
			cerr << "Error in allocateVirtualNetworks function: Undefine allocation system" << endl;
			exit(-1);
		}
	}
}

bool SubstractNetwork::greedyMethod( struct ScheduleElement se ){
	
	for( int i = 0; i < m; ++i )
		nodes[i].used = false;
	
	struct Node* vn_nodes = se.vn->getNodeList();
	int vn_m = se.vn->getNumberOfNodes();
	
	qsort( vn_nodes, vn_m, sizeof(struct Node), greedyMoreProcessingNodeFirst );
	
	qsort( nodes, m, sizeof(struct Node), greedyMoreProcessingNodeFirst );
	
	for( int i = 0; i < vn_m; ++i ){
		if( vn_nodes[i].target_node == -1 ){
			for( int j = 0; j < m; ++j ){
				if( vn_nodes[i].processing <= nodes[j].processing ){
					if( !nodes[j].used  ){
						vn_nodes[i].target_node = nodes[j].id;
						nodes[j].used = true;
						break;
					}
				}
				else{
					if( verbose )
						cout << "There is not enough processing resources for VN " << se.vn_id << ". Request postponed." << endl;
					return false;
				}
			}
		}
	}
	
	Edge*** vn_graph = se.vn->getGraph();
	
	
	for( int i = 0; i < m; ++i )
		for( int j = 0; j < m; ++j )
			if( graph[i][j] != NULL )
				graph[i][j]->gama = 0;
	
	for( int i = 0; i < vn_m; ++i ){
		for( int j = i; j < vn_m; ++j ){
			if( vn_graph[i][j] != NULL ){
				int v1, v2;
				v1 = v2 = -1;
				for( int k = 0; k < vn_m; ++k ){
					if( vn_nodes[k].id == i )
						v1 = vn_nodes[k].target_node;
					else if( vn_nodes[k].id == j )
						v2 = vn_nodes[k].target_node;
				}
				if( v1 == -1 || v2 == -1 ){
					cerr << "Error in function greedyMethod: There is a allocated virtual node without correspent entrance in virtual graph." << endl;
					exit(-1);
				}
				if( !buildPath( v1, v2, &vn_graph[i][j]->sn_path, vn_graph[i][j]->bandwidth ) ){
					if( verbose )
						cout << "There is not enough bandwidth resources for VN " << se.vn_id << ". Request postponed." << endl;
					return false;
				}
				if( vn_graph[i][j]->sn_path->front() != v1 || vn_graph[i][j]->sn_path->back() != v2 ){
					cerr << "Error in function greedyMethod: The begin and end of path does not correspond to begin and end vertices." << endl;
					exit(-1);
				}
				//if the request is allocated, it updates gama values on the substract network
				if( vn_graph[i][j]->sn_path != NULL ){
					list<int>::iterator v1, v2;
					v1 = v2 = vn_graph[i][j]->sn_path->begin();
					++v2;
					while( v2 != vn_graph[i][j]->sn_path->end() ){
						if( graph[*v1][*v2] != NULL ){
							graph[*v1][*v2]->gama += vn_graph[i][j]->bandwidth;
							graph[*v2][*v1]->gama += vn_graph[i][j]->bandwidth;
							++v2; ++v1;
						}
						else{
							cerr << "Error in function greedyMethod, while updating gama values: A invalid substract path was builded." << endl;
							exit(-1);
						}
					}
				}
			}
		}
	}
	
	qsort( nodes, m, sizeof( struct Node ), compareIds );
	for( int i = 0; i < vn_m; ++i ){
		if( vn_nodes[i].target_node != -1 ){
			nodes[vn_nodes[i].target_node].processing -= vn_nodes[i].processing;
		}
		else{
			cerr << "Error in function greedyMethod: There is a allocated virtual node without correspondent substract networkt node." << endl;
			exit(-1);
		}
	}
	
	for( int i = 0; i < vn_m; ++i ){
		for( int j = i; j < vn_m; ++j ){
			if( vn_graph[i][j] != NULL ){
				if( vn_graph[i][j]->sn_path != NULL ){
					list<int>::iterator v1, v2;
					v1 = v2 = vn_graph[i][j]->sn_path->begin();
					++v2;
					while( v2 != vn_graph[i][j]->sn_path->end() ){
						if( graph[*v1][*v2] != NULL ){
							graph[*v1][*v2]->bandwidth -= vn_graph[i][j]->bandwidth;
							graph[*v2][*v1]->bandwidth -= vn_graph[i][j]->bandwidth;
							++v2; ++v1;
						}
						else{
							cerr << "Error in function greedyMethod: A invalid substract path was builded." << endl;
								exit(-1);
						}
					}
				}
				else{
					cerr << "Error in function greedyMethod: There is a allocated virtual link with empty path." << endl;
					exit(-1);
				}
			}
		}
	}
	
	if( verbose )
		cout << "VN " << se.vn_id << " allocated" << endl;
	
	active_vns.push_back( se );
	sum_prizes_attended_requests += se.real_prize;
	total_attended_requests++;
	
	return true;
}

bool SubstractNetwork::buildPath( int v1, int v2, list<int>** path, int min_bw ){
	
	
	vector<struct V> Q(m);
	for( int i = 0; i < m; ++i ){
		Q[i].d = INT_MAX;
		Q[i].pi = -1;
	}
	Q[v1].d = 0;
	list<int> A;
	
	int sizeQ = m;
	while( sizeQ > 0 ){
		int min = INT_MAX;
		int u;
		for( int i = 0; i < m; ++i ){
			if( min > Q[i].d && Q[i].d != -1 ){
				min = Q[i].d;
				u = i;
			}
		}
		Q[u].d = -1;
		--sizeQ;
		
		A.push_back( u );
		for( int v = 0; v < m; ++v ){
			if( graph[u][v] != NULL && Q[v].d != -1 && graph[u][v]->bandwidth-graph[u][v]->gama >= min_bw ){
				if( Q[v].d > Q[u].d + 1 ){
					Q[v].d = Q[u].d + 1;
					Q[v].pi = u;
				}
			}
		}
	}
	
	if( Q[v2].pi == -1 )
		return false;
	
	*path = new list<int>;
	
	(*path)->push_front( v2 );

	struct V it = Q[v2];
	while( it.pi != v1 ){
		if( it.pi == -1 ){
			cerr << "Error in function buildPath: path builded breaks bandwidth constraint." << endl;
			exit(-1);
		}
		(*path)->push_front( it.pi );
		it = Q[it.pi];
	}
	(*path)->push_front( v1 );

	return true;
}

bool SubstractNetwork::tabuSearch( struct ScheduleElement se ){
	//cout << se.vn_id << endl;
	qsort( nodes, m, sizeof(struct Node), greedyMoreProcessingNodeFirst );
	qsort( se.vn->getNodeList(), se.vn->getNumberOfNodes(), sizeof(struct Node), greedyMoreProcessingNodeFirst );
	
	TabuSearchHeuristic ts( this, se.vn );
	if( ts.solve() ){
	
		ts.copySolution( se.vn->getNodeList(), se.vn->getGraph() );
		
		struct Node* vn_nodes = se.vn->getNodeList();
		int vn_m = se.vn->getNumberOfNodes();
		
		qsort( nodes, m, sizeof( struct Node ), compareIds );
		//cout << endl;
		for( int i = 0; i < vn_m; ++i ){
			if( vn_nodes[i].target_node != -1 ){
				nodes[vn_nodes[i].target_node].processing -= vn_nodes[i].processing;
				//cout << "(" << vn_nodes[i].id << "," << nodes[vn_nodes[i].target_node].id << ") ";
			}
			else{
				cerr << "Error in function tabuSearch: There is a allocated virtual node without correspondent substract networkt node." << endl;
				exit(-1);
			}
		}
		//cout << endl;
		
		Edge*** vn_graph = se.vn->getGraph();
		
		for( int i = 0; i < vn_m; ++i ){
			for( int j = i; j < vn_m; ++j ){
				if( vn_graph[i][j] != NULL ){
					if( vn_graph[i][j]->sn_path != NULL ){
						list<int>::iterator v1, v2;
						v1 = v2 = vn_graph[i][j]->sn_path->begin();
						++v2;
						while( v2 != vn_graph[i][j]->sn_path->end() ){
							//cout << "(" << *v1 << "," << *v2 << ") ";
							if( graph[*v1][*v2] != NULL ){
								graph[*v1][*v2]->bandwidth -= vn_graph[i][j]->bandwidth;
								graph[*v2][*v1]->bandwidth -= vn_graph[i][j]->bandwidth;
								++v2; ++v1;
							}
							else{
								cerr << "Error in function tabuSearch: A invalid substract path was builded." << endl;
								exit(-1);
							}
						}
						//cout << endl;
					}
					else{
						cerr << "Error in function tabuSearch: There is a allocated virtual link with empty path." << endl;
						exit(-1);
					}
				}
			}
		}
		active_vns.push_back( se );
		sum_prizes_attended_requests += se.real_prize;
		total_attended_requests++;
		
		if( verbose )
			cout << "VN " << se.vn_id << " allocated" << endl;
		
		return true;
	}
	else{
		if( verbose )
			cout << "Tabu Search Heuristic could not allocates vn " << se.vn_id << ". Request postponed." << endl;
		return false;
	}
	
}


SubstractNetwork::SubstractNetwork( const SubstractNetwork& sn ) : Network( sn.m, sn.n, sn.prize ){
	this->sum_prizes_attended_requests = 0;
	this->total_attended_requests = 0;
	
	for( int i = 0; i < sn.m; ++i )
		this->nodes[i] = sn.nodes[i];
	
	for( int i = 0; i < sn.m; ++i )
		for( int j = 0; j < sn.m; ++j )
			if( sn.graph[i][j] != NULL ){
				this->graph[i][j] = new struct Edge;
				*this->graph[i][j] = *sn.graph[i][j];
			}
}